#include "LargeNumCalcImpl.h"
#include "LarNumber.h"

// 大数加法
string LargeNumCalcImpl::add(const string& a, const string& b) {
    // 处理符号
    bool isNegative = (a[0] == '-' && b[0] != '-') || (a[0] != '-' && b[0] == '-');
    string num1 = a, num2 = b;
    if (num1[0] == '-') num1 = num1.substr(1);
    if (num2[0] == '-') num2 = num2.substr(1);

    // 处理小数点
    auto [aInt, aFrac] = splitNumber(num1);
    auto [bInt, bFrac] = splitNumber(num2);

    // 对齐小数部分
    int maxFracLen = max(aFrac.length(), bFrac.length());
    string alignedAFrac = aFrac;
    string alignedBFrac = bFrac;
    alignedAFrac.resize(maxFracLen, '0');
    alignedBFrac.resize(maxFracLen, '0');

    string intResult = addStrings(aInt, bInt);
    string fracResult;

    if (maxFracLen > 0) {
        fracResult = addStrings(alignedAFrac, alignedBFrac);
        // 处理小数部分的进位
        if (fracResult.length() > static_cast<size_t>(maxFracLen)) {
            intResult = addStrings(intResult, "1");
            fracResult = fracResult.substr(1);
        }
    }

    // 组合结果
    string result;
    if (maxFracLen > 0) {
        result = intResult + "." + fracResult;
    } else {
        result = intResult;
    }

    // 添加符号
    if (isNegative) {
        result = '-' + result;
    }

    return result;
}

// 辅助函数：字符串加法
string LargeNumCalcImpl::addStrings(const string& num1, const string& num2) {
    int i = num1.length() - 1;
    int j = num2.length() - 1;
    int carry = 0;
    string result;

    while (i >= 0 || j >= 0 || carry > 0) {
        int digit1 = (i >= 0) ? (num1[i--] - '0') : 0;
        int digit2 = (j >= 0) ? (num2[j--] - '0') : 0;
        int sum = digit1 + digit2 + carry;

        result = char(sum % 10 + '0') + result;
        carry = sum / 10;
    }

    return result.empty() ? "0" : result;
}

// 大数减法
string LargeNumCalcImpl::subtract(const string& a, const string& b) {
    // 检查是否需要处理负数
    if (a[0] == '-' && b[0] != '-') {
        return '-' + add(a.substr(1), b);
    } else if (a[0] != '-' && b[0] == '-') {
        return add(a, b.substr(1));
    } else if (a[0] == '-' && b[0] == '-') {
        return subtract(b.substr(1), a.substr(1));
    }

    // 处理小数点
    auto [aInt, aFrac] = splitNumber(a);
    auto [bInt, bFrac] = splitNumber(b);

    // 对齐小数部分
    int maxFracLen = max(aFrac.length(), bFrac.length());
    string alignedAFrac = aFrac;
    string alignedBFrac = bFrac;
    alignedAFrac.resize(maxFracLen, '0');
    alignedBFrac.resize(maxFracLen, '0');

    // 比较两个数的大小
    int comparison = compareNumbers(a, b);
    if (comparison == -1) {
        return '-' + subtract(b, a);
    }

    // 如果有小数部分
    if (maxFracLen > 0) {
        // 先处理小数部分
        string fracResult;
        int borrow = 0;

        for (int i = maxFracLen - 1; i >= 0; --i) {
            int digitA = alignedAFrac[i] - '0';
            int digitB = alignedBFrac[i] - '0';

            digitA -= borrow;

            if (digitA < digitB) {
                digitA += 10;
                borrow = 1;
            } else {
                borrow = 0;
            }

            fracResult = to_string(digitA - digitB) + fracResult;
        }

        // 处理整数部分
        string intResult = subtractStrings(aInt, bInt, borrow);

        // 去除结果中的前导零和末尾零
        if (!fracResult.empty()) {
            // 去除末尾零
            size_t lastNonZero = fracResult.find_last_not_of('0');
            if (lastNonZero != string::npos) {
                fracResult = fracResult.substr(0, lastNonZero + 1);
            } else {
                fracResult = "0";
            }
        }

        // 组合整数和小数部分
        if (fracResult.empty()) {
            return intResult;
        } else {
            return intResult + "." + fracResult;
        }
    } else {
        return subtractStrings(a, b, 0);
    }
}

// 比较两个大数的大小
// int LargeNumCalcImpl::compareNumbers(const string& a, const string& b) {
//     if (a.size() > b.size()) return 1;
//     if (a.size() < b.size()) return -1;
//     for (size_t i = 0; i < a.size(); ++i) {
//         if (a[i] > b[i]) return 1;
//         if (a[i] < b[i]) return -1;
//     }
//     return 0;
// }

// 分割数字为整数部分和小数部分
pair<string, string> LargeNumCalcImpl::splitNumber(const string& num) {
    size_t dotPos = num.find('.');
    if (dotPos == string::npos) {
        return {num, ""};
    } else {
        return {num.substr(0, dotPos), num.substr(dotPos + 1)};
    }
}

// 处理整数部分的减法
string LargeNumCalcImpl::subtractStrings(const string& a, const string& b, int borrow) {
    string result;
    int i = a.size() - 1;
    int j = b.size() - 1;
    int currentBorrow = borrow;

    while (i >= 0 || j >= 0 || currentBorrow > 0) {
        int digitA = (i >= 0) ? (a[i--] - '0') : 0;
        int digitB = (j >= 0) ? (b[j--] - '0') : 0;

        digitA -= currentBorrow;
        if (digitA < digitB) {
            digitA += 10;
            currentBorrow = 1;
        } else {
            currentBorrow = 0;
        }

        result = to_string(digitA - digitB) + result;
    }

    // 去除前导零
    size_t start = result.find_first_not_of('0');
    if (start != string::npos) {
        result = result.substr(start);
    } else {
        result = "0";
    }

    return result;
}

// 乘法
string LargeNumCalcImpl::multiply(const string& num1, const string& num2) {
    // 预处理（符号/小数点处理）
    PreProcessResult processed = LargeNumCalcImpl::preProcess(num1, num2);
    
    // 选择乘法算法
    string result;
    if (processed.x.length() > 50 || processed.y.length() > 50) {
        result = karatsubaMultiply(processed.x, processed.y);
    } else {
        result = multiplyStrings(processed.x, processed.y);
    }

    // 后处理（添加小数点和符号）
    return postProcess(result, processed.sign, processed.decimalPlaces);
}

// 预处理函数实现
LargeNumCalcImpl::PreProcessResult LargeNumCalcImpl::preProcess(const string& a, const string& b) {
    string a_clean = a;
    string b_clean = b;
    
    // 符号处理
    bool isNegative = false;
    if (a_clean[0] == '-') {
        isNegative = !isNegative;
        a_clean = a_clean.substr(1);
    }
    if (b_clean[0] == '-') {
        isNegative = !isNegative;
        b_clean = b_clean.substr(1);
    }

    // 小数点处理
    int decimalPlaces = 0;
    size_t dotPos;
    
    if ((dotPos = a_clean.find('.')) != string::npos) {
        decimalPlaces += a_clean.length() - dotPos - 1;
        a_clean.erase(dotPos, 1);
    }
    
    if ((dotPos = b_clean.find('.')) != string::npos) {
        decimalPlaces += b_clean.length() - dotPos - 1;
        b_clean.erase(dotPos, 1);
    }

    // 移除前导零
    size_t start = a_clean.find_first_not_of('0');
    a_clean = (start == string::npos) ? "0" : a_clean.substr(start);
    
    start = b_clean.find_first_not_of('0');
    b_clean = (start == string::npos) ? "0" : b_clean.substr(start);

    return {
        isNegative ? "-" : "",
        a_clean,
        b_clean,
        decimalPlaces
    };
}

// 后处理函数实现
string LargeNumCalcImpl::postProcess(const string& result, const string& sign, int decimalPlaces) {
    string processed = result;
    
    // 添加小数点
    if (decimalPlaces > 0) {
        int position = processed.length() - decimalPlaces;
        if (position > 0) {
            processed.insert(position, ".");
        } else {
            processed = "0." + string(-position, '0') + processed;
        }
        
        // 移除小数部分尾部的零
        size_t dotPos = processed.find('.');
        if (dotPos != string::npos) {
            size_t end = processed.find_last_not_of('0');
            if (end == dotPos) {
                processed = processed.substr(0, dotPos);
            } else if (end > dotPos) {
                processed = processed.substr(0, end + 1);
            }
        }
    }
    
    // 添加符号
    if (sign == "-" && processed != "0") {
        processed = sign + processed;
    }
    
    return processed;
}

// Karatsuba乘法算法
string LargeNumCalcImpl::karatsubaMultiply(const string& x, const string& y) {
    // 基础情况处理
    if (x.length() <= 50 || y.length() <= 50) {
        return multiplyStrings(x, y);
    }

    size_t m = max(x.length(), y.length());
    size_t m2 = m / 2;

    // 分解数字
    auto [high1, low1] = splitNumber(x, m2);
    auto [high2, low2] = splitNumber(y, m2);

    // 递归计算三个乘积
    string z0 = karatsubaMultiply(low1, low2);
    string z1 = karatsubaMultiply(addStrings(low1, high1), addStrings(low2, high2));
    string z2 = karatsubaMultiply(high1, high2);

    // 组合结果
    string term1 = z2 + string(2 * m2, '0');
    string term2 = subtractStrings(subtractStrings(z1, z2, 0), z0, 0) + string(m2, '0');
    
    return addStrings(addStrings(term1, term2), z0);
}

// 拆分数字
pair<string, string> LargeNumCalcImpl::splitNumber(const string& num, int position) {
    if (position >= static_cast<int>(num.size())) {
        return {"0", num};
    }
    
    int splitPos = num.size() - position;
    return {
        num.substr(0, splitPos),
        num.substr(splitPos)
    };
}

// 字符串乘法（普通算法）
string LargeNumCalcImpl::multiplyStrings(const string& num1, const string& num2) {
    if (num1 == "0" || num2 == "0") return "0";
    
    int m = num1.size(), n = num2.size();
    vector<int> res(m + n, 0);
    
    for (int i = m - 1; i >= 0; i--) {
        for (int j = n - 1; j >= 0; j--) {
            int mul = (num1[i] - '0') * (num2[j] - '0');
            int p1 = i + j, p2 = i + j + 1;
            int sum = mul + res[p2];
            
            res[p2] = sum % 10;
            res[p1] += sum / 10;
        }
    }
    
    // 转换为字符串并移除前导零
    string result;
    for (int num : res) {
        if (!(result.empty() && num == 0)) {
            result.push_back('0' + num);
        }
    }
    
    return result.empty() ? "0" : result;
}

// 除法
string LargeNumCalcImpl::divide(const string& num1, const string& num2) {
    // 处理特殊情况
    if (num2 == "0") throw invalid_argument("除数不能为零");
    if (num1 == "0") return "0";
    
    string a = num1;
    string b = num2;
    
    // 处理符号
    bool isNegative = false;
    if (a[0] == '-') {
        isNegative = !isNegative;
        a = a.substr(1);
    }
    if (b[0] == '-') {
        isNegative = !isNegative;
        b = b.substr(1);
    }
    
    // 处理小数点，将小数转为整数
    int decimalShift = 0;
    size_t dotPos;
    
    if ((dotPos = a.find('.')) != string::npos) {
        decimalShift -= a.length() - dotPos - 1;
        a.erase(dotPos, 1);
    }
    
    if ((dotPos = b.find('.')) != string::npos) {
        decimalShift += b.length() - dotPos - 1;
        b.erase(dotPos, 1);
    }
    
    // 去掉前导零
    size_t start = a.find_first_not_of('0');
    a = (start == string::npos) ? "0" : a.substr(start);
    
    start = b.find_first_not_of('0');
    b = (start == string::npos) ? "0" : b.substr(start);
    
    // 为了保证足够精度，为被除数增加足够的零
    const int precision = 100; // 最大支持100位小数
    a += string(precision, '0');
    
    // 执行长除法
    string quotient = longDivision(a, b);
    
    // 处理小数点位置
    string result = quotient;
    int decimalPos = result.length() - precision + decimalShift;
    
    if (decimalPos <= 0) {
        // 小数点在最前面
        result = "0." + string(-decimalPos, '0') + result;
    } else if (decimalPos < static_cast<int>(result.length())) {
        // 小数点在中间
        result.insert(decimalPos, ".");
    } else {
        // 小数点在后面或没有小数部分
        result += string(decimalPos - result.length(), '0');
    }
    
    // 去除末尾的零和无意义的小数点
    size_t dotPosition = result.find('.');
    if (dotPosition != string::npos) {
        // 移除小数部分尾部的零
        size_t end = result.find_last_not_of('0');
        if (end == dotPosition) {
            result = result.substr(0, dotPosition);
        } else if (end > dotPosition) {
            result = result.substr(0, end + 1);
        }
    }
    
    // 添加符号
    if (isNegative && result != "0") {
        result = "-" + result;
    }
    
    return result;
}

// 辅助函数：长除法
string LargeNumCalcImpl::longDivision(const string& dividend, const string& divisor) {
    string result;
    string remainder;
    
    for (size_t i = 0; i < dividend.length(); i++) {
        remainder += dividend[i];
        
        // 移除前导零
        size_t start = remainder.find_first_not_of('0');
        if (start == string::npos) {
            remainder = "0";
        } else {
            remainder = remainder.substr(start);
        }
        
        int quotientDigit = 0;
        
        // 找到当前位的商
        while (compareNumbers(remainder, divisor) >= 0) {
            remainder = subtractStrings(remainder, divisor, 0);
            quotientDigit++;
        }
        
        result += to_string(quotientDigit);
    }
    
    // 移除前导零
    size_t start = result.find_first_not_of('0');
    if (start == string::npos) {
        return "0";
    }
    return result.substr(start);
}

// 辅助函数：比较两个数的大小（复用乘法代码中的实现）
int LargeNumCalcImpl::compareNumbers(const string& a, const string& b) {
    // 移除前导零
    string aClean = a;
    string bClean = b;
    
    size_t start = aClean.find_first_not_of('0');
    aClean = (start == string::npos) ? "0" : aClean.substr(start);
    
    start = bClean.find_first_not_of('0');
    bClean = (start == string::npos) ? "0" : bClean.substr(start);
    
    // 比较长度
    if (aClean.length() > bClean.length()) return 1;
    if (aClean.length() < bClean.length()) return -1;
    
    // 逐位比较
    for (size_t i = 0; i < aClean.length(); i++) {
        if (aClean[i] > bClean[i]) return 1;
        if (aClean[i] < bClean[i]) return -1;
    }
    
    return 0;
}

// 次方
string LargeNumCalcImpl::power(const string& base, const string& exponent) {
    // 处理特殊情况
    if (exponent == "0") return "1";
    if (base == "0") return "0";
    // 将base字符串转换为const uint64_t baseNum, 并处理异常
    try {
        const uint64_t baseNum = stoull(base);
    
        const int numExponent = stoi(exponent);
        LarNumber bigBase(baseNum);
        LarNumber cppResult = LarNumber::bigPowerCPP(bigBase, numExponent);
        
        return cppResult.toString();
    } catch (const invalid_argument& e) {
        throw invalid_argument("指数或底数字符串转换为数字失败");
    }
}

// 辅助函数：大数除以2
string LargeNumCalcImpl::divideByTwo(const string& numStr) {
    string result;
    int carry = 0;
    
    for (char c : numStr) {
        int digit = (c - '0') + carry * 10;
        int quotient = digit / 2;
        carry = digit % 2;
        
        // 跳过前导零
        if (!result.empty() || quotient != 0) {
            result.push_back('0' + quotient);
        }
    }
    
    return result.empty() ? "0" : result;
}

// 阶乘
string LargeNumCalcImpl::factorial(const string& num) {
    try {
        if (num == "0" || num == "1") return "1";
        // 将num转换成int

        LarNumber ret = LarNumber::bigFactorialCPP(std::stoi(num));

        return ret.toString();
    } catch (const invalid_argument& e) {
        throw invalid_argument("阶乘数字符串转换为数字失败");
    }
}